package 简单.动态规划;

/**
 * 题目描述：假设农场中成熟的母牛每年都会生 1 头小母牛，并且永远不会死。第一年有 1
 * 只母牛，从第二年开始，母牛开始生小母牛。每只小母牛 3 年之后成熟又可以生小母牛
 * 。给定整数 N，求 N 年后牛的数量。
 * <p>
 * 1，定义子问题
 * 到第i年的牛的数量
 * 2，递推关系
 * 第一年有1只牛
 * 第二年有2只牛
 * 第三年有3只牛
 * 第四年年有三年前小牛（已经成熟）和母牛生的小牛，加上一年前的牛
 * <p>
 * 第i年牛的数量等于前一年牛的数量（前一年母牛生的小牛不做计算，包含在前三年的母牛里面）+今年新增的小牛（三年前的小牛和母牛）
 * d[i]=dp[i-1]+dp[i-4]
 * 3，顺序
 * 从首到尾
 * 4，空间优化
 */
public class 母牛生产 {

    public static void main(String[] args) {

        int prod = efficientProd(5);
        System.out.println(prod);
    }

    //动态规划
    public static int prod(int n) {
        //防止数组越界
        int[] dp = new int[n + 4];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for (int i = 4; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 3];
        }
        return dp[n];
    }

    //空间优化
    public static int efficientProd(int n) {
        if (n < 4) {
            return n;
        }
        int pre3 = 1, pre2 = 2, pre1 = 3, cur;
        for (int i = 4; i <= n; i++) {
            cur = pre1 + pre3;
            pre3 = pre2;
            pre2 = pre1;
            pre1 = cur;
        }
        return pre1;
    }
}
